package previous.Test_0311;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //前k个高频单词
    public List<String> topKFrequent(String[] words, int k) {
           //统计单词个数：哈希表
        HashMap<String,Integer> map=new HashMap<>();
        for(String s:words){
            map.put(s,map.getOrDefault(s,0)+1);
        }
        //创建堆：如果频次相同，那么按照字典序排序，用大跟堆
        //不同用小跟对
        PriorityQueue<Map.Entry<String,Integer>> q=new PriorityQueue<>(
                (a,b) -> a.getValue().equals(b.getValue())?
                        b.getKey().compareTo(a.getKey()):
                        a.getValue()- b.getValue()
        );
        //让元素依次进堆
        for(Map.Entry<String,Integer> entry: map.entrySet()){
            q.offer(entry);
            if(q.size()>k){
                q.poll();
            }
        }
        //提取
        List<String> l=new ArrayList<>();
        while(!q.isEmpty()){
            l.add(q.poll().getKey());
        }
        Collections.reverse(l);
        return l;
    }
}
